/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package org.dusin.teachassist.matchalg;

/**
 * 最长公共子序列
 * @author dusin
 */
public class MaxCommonSequence implements MatchStrategy{

    @Override
    public double getMatchDegree(String a, String b) {
        double result;
        int[][] ma = longestCommonSubsequence(a,b);
        sb = new StringBuilder();
        print(ma, a, b, a.length(), b.length());
        //System.out.println(sb.toString());
        result  = (double)sb.length()/(double)a.length();
        return result;
    }
  
    @Override
    public int getMatchLength(String a,String b){
        int[][] ma = longestCommonSubsequence(a,b);
        sb = new StringBuilder();
        print(ma, a, b, a.length(), b.length());
        return sb.length();
    }
    // 假如返回两个字符串的最长公共子序列的长度
    private static int[][] longestCommonSubsequence(String str1, String str2) {
        int[][] matrix = new int[str1.length() + 1][str2.length() + 1];//建立二维矩阵
        // 初始化边界条件
        for (int i = 0; i <= str1.length(); i++) {
            matrix[i][0] = 0;//每行第一列置零
        }
        for (int j = 0; j <= str2.length(); j++) {
            matrix[0][j] = 0;//每列第一行置零
        }
        // 填充矩阵
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    matrix[i][j] = matrix[i - 1][j - 1] + 1;
                } else {
                    matrix[i][j] = (matrix[i - 1][j] >= matrix[i][j - 1] ? matrix[i - 1][j]
                            : matrix[i][j - 1]);
                }
            }
        }
        return matrix;
    }
    
    StringBuilder sb ;
    //根据矩阵输出LCS
    public  void print(int[][] opt, String X, String Y, int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }
        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
            print(opt, X, Y, i - 1, j - 1);
            sb.append(X.charAt(i - 1));
        } else if (opt[i - 1][j] >= opt[i][j]) {
            print(opt, X, Y, i - 1, j);
        } else {
            print(opt, X, Y, i, j - 1);
        }
    }
}
